package algorithm.Sort;

import java.io.*;

/**
 * 这里我们使用了ACM的IO处理方式
 * 给出了递归和非递归两种方式
 * 递归和非递归都是对递归序构成的二叉树的遍历，递归是深度优先遍历，非递归是广度优先遍历
 */
public class MergeSort {

    public static int MAX=501;
    public static int[] arr=new int[MAX];
    //过渡数组help
    public static int[] help=new int[MAX];
    //每一个数组的长度
    public static int n;

    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in=new StreamTokenizer(br);
        PrintWriter out=new PrintWriter(new ObjectOutputStream(System.out));

        in.nextToken();
        while(in.nextToken()!=StreamTokenizer.TT_EOF){
            n=(int)in.nval;
            for(int i=0;i<n;i++){
                in.nextToken();
                arr[i]=(int)in.nval;
            }
            mergeSort(0,n-1);
            for(int i=0;i<n-1;i++){
                out.print(arr[i]+'i');
            }
            out.print(arr[n-1]);
        }
        out.flush();
        out.close();
        br.close();
    }

    public static int[] sort(int[] nums){
        if(nums.length>1){
            mergeSort(0,nums.length-1);
        }
        return nums;
    }
    /**
     * 递归的归并排序
     */
    public static void mergeSort(int l,int r){
        if(l==r){
            return;
        }
        int m=(l+r)/2;
        mergeSort(l,m);
        mergeSort(m+1,r);
        merge(l,r,m);
    }

    public static void mergeSortWithStack(){

        //<<=1 右移一位并保存，相当于乘以2
        //这里不难得到，外循环共执行log(n)次
        for(int l,m,r,step=1;step<n;step<<=1){
            l=0;
            while(l<n){
                m=l+step-1;
                if(m+1>=n) break;
                //右开，m+step即l+step-1+step-1
                r=Math.min(m+step,n-1);
                merge(l,r,m);
                l=r+1;
            }
        }

    }

    /**
     * 合并过程
     * 先放在过渡数组help中，最后填充到arr里
     * m为两个数组之间的分隔
     */
    public static void merge(int l,int r,int m){
        int i=l;
        int a=l;
        int b=m+1;
        while(a<=m&&b<=r){
            help[i]= Math.min(arr[a], arr[b]);
            i++;
            a++;
            b++;
        }
        while(a<=m){
            help[i]=arr[a];
            i++;
            a++;
        }
        while(b<=r){
            help[i]=arr[b];
            i++;
            b++;
        }
        for(i=l;i<=r;i++){
            arr[i]=help[i];
        }
    }


}
